package com.lw.leetcode.binary.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * b
 * arr
 * 2563. 统计公平数对的数目
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/12 16:47
 */
public class CountFairPairs {

    public static void main(String[] args) {
        CountFairPairs test = new CountFairPairs();

        // 6
        int[] arr = {0, 1, 4, 4, 5, 7};
        int lower = 3;
        int upper = 6;

        long l = test.countFairPairs(arr, lower, upper);
        System.out.println(l);
    }

    private int[] nums;

    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        this.nums = nums;
        int length = nums.length - 1;
        long sum = 0;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int min = findMin(lower - num - 1, i + 1);
            if (min == -1) {
                continue;
            }
            int max = findMax(upper - num + 1, i + 1);
            if (max == -1) {
                continue;
            }
//            System.out.println(nums[i] + "  " + max + "  " + min);
            sum += (max - min + 1);
        }
        return sum;
    }

    private int findMin(int t, int st) {
        int end = nums.length - 1;
        if (nums[end] <= t) {
            return -1;
        }
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (nums[m] <= t) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return st;
    }

    private int findMax(int t, int st) {
        int end = nums.length - 1;
        if (nums[st] >= t) {
            return -1;
        }
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

}
